package architect.datastructure;

/**
 * 单链表
 *
 * @author guanxin
 * @date 2018/5/7 14:44
 */

public class SingleLinkedList {
    // 链表节点
    private class Node {
        Object item; // 节点元素
        Node next;   // 下一节点

        public Node() {
        }

        public Node(Object item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    Node first;
    Node last;
    int size;

    public SingleLinkedList() {
        this.first = null;
        this.last = null;
    }

    public SingleLinkedList(Object o) {
        first = new Node(o, null);
        last = first;
        size++;
    }

    public void checkIndex(int index) {
        if (index < 0 || index >= size) {
            try {
                throw new Exception("索引超界");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }

    public Node getNode(int index) {
        checkIndex(index);
        Node node = this.first;
        if (first != null) {
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
        }
        return node;
    }

    public int getIndex(Object o) {
        Node node = first;
        if (first != null) {
            int i;
            for (i = 0; i < size; i++) {
                if (node.item.equals(o))
                    break;
                node = node.next;
            }
            return i;
        } else {
            return -1;
        }
    }

    public void add(Object o) {
        Node node = new Node(o, null);
        if (last != null)
            last.next = node;
        if (first == null)
            first = node;
        last = node;
        size++;
    }

    public void traverse() {
        Node node = first;
        if (first != null) {
            do {
                System.out.println("->[" + first.next.item + "]");
                node = node.next;
            } while (node != null);
        }
    }

    public int size() {
        return size;
    }

    public void clear() {
        if (first != null) {
            while (first.next != null) {
                first.next = first.next.next;
            }
            last = first;
            size = 0;
            System.gc();
        }
    }

    public void add(int index, Object o) {
        checkIndex(index);
        if (first == null)
            add(o);
        else {
            Node originalNode = getNode(index);
            Node node = new Node(o, originalNode.next);
            originalNode.next = node;
        }
        size++;
    }

    public void remove(int index) {
        checkIndex(index);
        if (index == 0)
            first = first.next;
        else {
            Node originalNode = getNode(index - 1);
            originalNode.next = originalNode.next.next;
        }
    }

    //判断链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    public void addFirst() {

    }

    public void addLast() {

    }

    public void removeFirst() {

    }

    public void removeLast() {

    }
}
